package org.datacoder.geocoding.datastructures.points

import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.*

class RangeTree {

    RangeTreeNode root
    int type

    public RangeTree(Collection<Jurisdiction> jurisdictions, int type){
        if(jurisdictions.size() == 0){      // Unnecessary.  However, keeps bootstrap
            return                          // from throwing fit with empty db.
        }
        this.type = type
        List<GeoPoint> geoPointsList = new ArrayList<GeoPoint>()
        for(juris in jurisdictions){
            geoPointsList.add(juris.toGeoPoint())
        }
        GeoPoint[] geoPoints = geoPointsList.toArray()
        Arrays.sort(geoPoints, new GeoPointComparator(type))
        root = createNode(geoPoints, 0, geoPoints.length)
    }

    public RangeTreeNode createNode(GeoPoint[] geoPoints, int startIndex, int endIndex){
        RangeTreeNode rtNode = new RangeTreeNode()
        int middle = (startIndex + endIndex)/2
        rtNode.discriminator = geoPoints[middle].retrieveValue(type)
        rtNode.minVal = geoPoints[startIndex].retrieveValue(type)
        rtNode.maxVal = geoPoints[endIndex - 1].retrieveValue(type)

        for(int i = startIndex; i < endIndex; i++){
            rtNode.jurisList.add(geoPoints[i].juris)
        }

        if(startIndex < middle){
            rtNode.left = createNode(geoPoints, startIndex, middle)
        }
        if((middle + 1) < endIndex){
            rtNode.right = createNode(geoPoints, middle, endIndex)
        }
        return rtNode
    }

    public Set<Jurisdiction> findPointsWithinInterval(double min, double max){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        Queue<RangeTreeNode> rtNodeQueue = new LinkedList<RangeTreeNode>()
        rtNodeQueue.offer(root)
        while(rtNodeQueue.peek() != null){
            RangeTreeNode currentNode = rtNodeQueue.poll()
            if((min <= currentNode.minVal) && (currentNode.maxVal <= max)){
                jurisdictions.addAll(currentNode.jurisList)
            }else{
                if(currentNode.left != null){
                    if(min <= currentNode.discriminator){
                        rtNodeQueue.offer(currentNode.left)
                    }
                }else{
                    if((min <= currentNode.minVal) && (currentNode.minVal <= max)){
                        jurisdictions.add(currentNode.jurisList.getFirst())
                    }
                }
                if(currentNode.right != null){
                    if(currentNode.discriminator <= max){
                        rtNodeQueue.offer(currentNode.right)
                    }
                }else{
                    if((min <= currentNode.maxVal) && (currentNode.maxVal <= max)){
                        jurisdictions.add(currentNode.jurisList.getLast())
                    }
                }
            }
        }
        return jurisdictions
    }
	
}

